import random
from collections import deque

# 棋盘尺寸
N = 8

# 定义马的八种日字移动方式
moves = [
    (2, 1), (2, -1), (-2, 1), (-2, -1),
    (1, 2), (1, -2), (-1, 2), (-1, -2)
]

# 检查位置是否在棋盘内
def is_valid(x, y):
    return 0 <= x < N and 0 <= y < N

# 使用 BFS 找到最短路径
def find_knight_path(start_x, start_y, end_x, end_y):
    queue = deque([(start_x, start_y, [])])
    visited = set((start_x, start_y))

    while queue:
        x, y, path = queue.popleft()
        path = path + [(x, y)]

        # 如果到达目标位置
        if (x, y) == (end_x, end_y):
            return path

        # 尝试所有可能的跳马移动
        for dx, dy in moves:
            nx, ny = x + dx, y + dy
            if is_valid(nx, ny) and (nx, ny) not in visited:
                visited.add((nx, ny))
                queue.append((nx, ny, path))

    return None  # 无法到达终点

# 程序入口
def main():
    # 随机起始位置
    start_x, start_y = random.randint(0, N-1), random.randint(0, N-1)
    end_x, end_y = N-1, N-1
    print(f"棋盘8行8列.....")
    print(f"起始位置: ({start_x}, {start_y})")
    print(f"目标位置: ({end_x}, {end_y})")

    path = find_knight_path(start_x, start_y, end_x, end_y)

    if path:
        print("跳马步骤:")
        for step in path:
            print(step)
    else:
        print("无法到达目标位置")

if __name__ == "__main__":
    main()
